A lower bound for bounded round quantum communication complexity of set disjointness

摘要

We prove a lower bound of Omega(n/k^4) for the communication complexity of a k-round two party bounded error quantum protocol with prior entanglement for the set disjointness problem.